s=[1,53,22,7,1,4,2,7,12]

#合并算法
def merge(r_pointer,l_pointer):
    #合并后的序列存放位置
    mergeList=[]

    r_pointer_process,l_pointer_process=0,0
    while r_pointer_process<len(r_pointer) and l_pointer_process<len(l_pointer):
        if r_pointer[r_pointer_process]<l_pointer[l_pointer_process]:
            mergeList.append(r_pointer[r_pointer_process])
            r_pointer_process+=1
        else:
            mergeList.append(l_pointer[l_pointer_process])
            l_pointer_process+=1
    if l_pointer_process==len(l_pointer):
        while r_pointer_process<len(r_pointer):
            mergeList.append(r_pointer[r_pointer_process])
            r_pointer_process+=1
    else:
        while l_pointer_process<len(l_pointer):
            mergeList.append(l_pointer[l_pointer_process])
            l_pointer_process+=1
    return mergeList


def Merge_sort(s):
    if len(s)<=1:
        return s
    #划分子序列
    midPointer=len(s)//2
    #分割左右序列
    r_pointer=Merge_sort(s[:midPointer])
    l_pointer=Merge_sort(s[midPointer:])
    return merge(l_pointer,r_pointer)
print(Merge_sort(s))
